import java.util.Scanner;

public class TestEclipse01 {
	public static void main(String[] args)
	{
		Scanner read = new Scanner(System.in);
		int n = read.nextInt();
		
		//方法一:递归
		int ans = fib(n);
		System.out.println(ans);
        //方法二：动态规划
        int[] dp = new dp[n+1];
        if(n<=1)
		System.out.println(1);
        dp[0] = 0;
        dp[1] = 1;
        for(int i=2; i<n+1; ++i)
        {
            dp[i] = dp[i-1] + dp[i-2]
        }
        //方法三：尾递归
        int ans2 = fib2(n);
        //方法四：动态规划的内存优化
        dp_i_1 = 0;
        dp_i_2 = 1;
        if(n<=1)
        return 1;
		System.out.println(1);
        for(int i=2; i<=n; ++i)
        {
            int dp_i = dp_i_1 + dp_i_2;
            dp_i_1 = dp_i_2;
            dp_i_2 = dp_i;
        }
        System.out.println(dp_i_2);

	}
	public static int fib(int n)
	{
		if(n <= 1)
		{
			return n;
		}
		return fib(n-1) + fib(n-2);	
	}


    public static int fib2(int n)
    {
        int[] memo = new int[n+1];
        if(n<=1)
        return n;
        return helper(memo,n)
    }
    public static int helper(int[] memo, int n)
    {
        if(memo[n] != 0)
        return memo[n];
        return helper(memo, n-1) + helper(memo,n-2);
    }
}
/*
完成！
复习完这个，我仿佛回到了高中的数学，我们数学作业纸下面有句话：

    学习数学要多做习题，边做边思索，先知其然，然后知其所以然。
                                                ——苏步青
现在我学算法也终究还是走了这个方式
*/